1. Field of the Invention
The invention relates generally to decision making and, alternatively, to learning, using a computing machine.
2. Discussion of the Related Art
Modern research and technology have made computing devices commonplace in the lives of many individuals. Many modern devices, appliances and conveniences include various amounts of computing or processing power. Devices that include computing capabilities often make decisions about objects based on whatever input data about the object is available to the device.
Such decisions may include, among others:
Selections of alternatives, help messages or hints about how to use the device, are presented to the user of the device;
Selections of entertainment, advertising, or other options or information to be shown to, or recorded for, the user;
Assessments or evaluations of whoever is using the device or of the environment or context in which the device is being used; or
Predictions about a system that the device attempts to model.
Many computing devices include a module or function that classifies objects, models preferences or evaluates alternatives. Such evaluators can decide which one or ones of a set of alternatives best apply to a particular object, as described by the input data available about that object, which may be quite limited.
Some evaluators are based on machine learning, that is, the evaluator has been trained as to what is the correct decision, or is trained over time as the device is actually used. In other cases, evaluators are hand crafted by the programmers who designed the device. In still other cases, experts formulate xe2x80x9crules of thumbxe2x80x9d or xe2x80x9coperating parameters,xe2x80x9d which are then entered into a computer program, model or expert system.
There are many known ways of representing or implementing a machine evaluator, including, among others; decision trees, belief networks, neural networks, static mathematical models, expert systems or computer programs. Many of these types of evaluators have known ways of using training data to train new instances of evaluators for new classification, selection or prediction problems. Typically, such training data includes many instances of input data from various example objects, with each instance labeled as to the alternative or alternatives that correctly apply to that object.
An evaluator is usually trained to be applied to objects not seen before. Thus, it is rare that one can speak confidently of having found the best or optimal evaluator. In fact, when the same machine learning model or type of evaluator is run using different batches of training data, different evaluators may be produced.
Further, some machine learning methods are non-deterministic, that is, they are likely to yield a different result each time the model is trained. Such methods include, among others; evolutionary training methods, population based training methods, genetic algorithms or genetic programming. For such methods, the result of the training process is typically not be a single evaluator. Rather, the result may be a number of evaluators, often ranked by some accuracy or fitness measure.
Thus, any particular machine decision problem can be approached using different types of evaluators, or using different instances of evaluators of the same type. One option is to select a single evaluator and use it exclusively. The type of evaluator selected may simply be chosen based on the preferences and familiarity of the person implementing the system.
A second option is to obtain a set of reasonably good evaluators for a particular machine decision problem and combine the result from each evaluator. Given the inaccuracy, uncertainty and other limitations of machine learning and machine decision making, this second approach may be advantageous for many problems.
However, this second option requires combining results from a number of evaluators into making an overall or aggregate decision. One way to combine decisions is to give each evaluator one vote, or a vote weighted by a factor such as the expected accuracy of that evaluator. If one alternative receives a majority of the weighted votes, then the majority should rule. However, there may not be a majority winner.
Another way to combine decisions is pluralistic voting, in which the alternative that receives the most votes is the aggregate decision, regardless of how few votes that alternative receives and regardless of how strong the other alternatives are. However, some observers of the 2000 U.S. presidential election feel there are significant problems with single vote pluralistic voting, especially when the voters are largely split as to their first preference.
Other observers cite the 1970 race for U.S. Senator from New York, in which a liberal Republican and a liberal Democrat split approximately 5 out of 9 votes. This split left conservative James Buckley winning with a plurality of approximately 4 out of 9 votes. To some observers, this result was unfair or inaccurate because a majority of the voters would have preferred either of the liberal candidates to Buckley. That claim could have been proven if the votes had recorded first, second and third preferences from each voter, or if Buckley and the candidate who came in second had faced a run off election.
A related effect occurs when a voter is pragmatically dishonest. A person may cast their vote for the candidate they prefer out of those who they feel have a realistic chance to win, rather than supporting a truly preferred long shot.
Training or designing a computer model to recognize consumer preferences, for example, is complex. It may be undesirable, difficult or infeasible to have such a model somehow adjust the vote it casts by taking into account other likely votes. A way to compute an aggregate decision, based on intermediate decisions as to which alternative or alternatives best apply to an object, has not been known to be available.
The present invention provides a solution to the problems identified above by providing an automated method and apparatus to employ intermediate decisions as to the application of alternatives to an object to compute an overall or aggregate decision.
According to the invention, at least two intermediate rankings are obtained, each of which ranks each of at least three alternatives with respect to an object. For each intermediate ranking, a corresponding series of preferences is initialized. Each series is ordered from a first preference to a last preference. Each series initially groups each alternative into a preference selected based on the corresponding intermediate ranking. In the case of a tie, each preference may include more than one alternative. Based on all the series of preferences, a weak alternative is selected and removed from each series. Each series is accordingly re-grouped into updated preferences, based on the intermediate ranking corresponding to the series.
When each series contains fewer than a first threshold number of alternatives, then the invention stops and the aggregate decision includes the alternatives remaining in the series. Otherwise, the method repeats the selecting, the removing, the re-grouping and the deciding until an aggregate decision is made.
Various embodiments of the invention include deciding the intermediate rankings based on a technique selected from: a machine learning technique; a decision tree; a belief network; a neural network; a static model; a program; an evolutionary training method; or some other technique. In some embodiments of the invention it may be advantageous to base different evaluators on different techniques.
Some embodiments of the invention can be applied to classification problems.
The alternatives include classifications of the object and the aggregate decision classifies the object.
Other embodiments of the invention can be applied to prediction problems.
The alternatives include a set of future behaviors of the object and the aggregate decision predicts a likely one or more of the future behaviors.
Yet other embodiments of the invention can be applied to selection problems. The alternatives include options and the aggregate decision selects one or more options based on the object.
In some embodiments of the invention, the selection of the weak alternative to be removed includes identifying which alternatives are preferred over other alternatives in pairwise votes or preference contests, and in every series the weak alternative loses to every other alternative. In other embodiments, a generalized criteria is used wherein the weak alternative is selected such that at least a first percentage of the alternatives are preferred over the weak alternative in at least a second percentage of the series.
In yet other embodiments of the invention, the selection of the weak alternative includes identifying which alternatives are included in the first preference (or first several preferences) of every series, and the weak alternative is in the first preference in no more series than any other alternative. In still other embodiments, a generalized criteria is used wherein the weak alternative is selected such that there is less than a selected percentage of the alternatives that are omitted from a set of first preferences more than the weak alternative is omitted from the set of first preferences. The set of first preferences includes one or more of the preference ranks within each series that are most preferred, or equivalently, that have the lowest rank numbers.
In some embodiments of the invention, the thresholds, percentages and sets of references used in the various elimination, selection and termination criteria are independent of each other. Various embodiments of the invention include selecting such thresholds, percentages and preference sets from: a predetermined number; a predetermined percentage of the alternatives; or a number that is adjusted during the operation of the method, among other options.
In other embodiments of the invention, the selection of the weak alternative includes identifying which alternatives are in the last preference (or last several preferences) of every series, and no other alternative is in the last preference in more series than the weak alternative. In other embodiments, a generalized criteria is used wherein the weak alternative is selected such that less than a selected percentage of the alternatives is in a set of last preferences more than the weak alternative is in the set of last preferences. The set of last preferences includes one of more of the preference ranks within each series that are least preferred, or equivalently, that have the highest rank numbers.
In yet other embodiments of the invention, the selection of the weak alternative includes giving to each alternative a number of points based on each preference in each series, the number of points decreasing for lower preferences, and the total points received by the weak alternative is no more than the points received by any other alternative. In still other embodiments, a more general criteria is used wherein the selection of the weak alternative includes calculating an average preference for each alternative, and the average preference of less than a percentage of the alternatives is higher than the average preference of the weak alternative.
In some embodiments of the invention, the selection of the weak alternative includes identifying which alternatives are included in a set of first preferences within each series, and less than a percentage of the series have the weak alternative in the set of first preferences.
Other embodiments of the invention include selecting a particular alternative to be included in the aggregate decision and removing that particular alternative from each series. Some of these embodiments select the particular alternative from: an alternative that is in the first preference of at least a second threshold number of the series; an alternative that is preferred over every other alternative in every series; or an alternative that is preferred over at least a first percentage of the alternatives in at least a second percentage of the series.
The various embodiments of invention may be embodied as a system, a hardware module, a software module, a method, or a media that provides instructions for a programmable device.